//全排列二（给定集合含重复元素，要求全排列中无重复元素） 力扣47
//回溯算法 树层去重（可排序后使用used数组或直接用unordered_set查找之前是否遍历过）
class Solution {
public:
	vector<vector<int>> ans;
	vector<int> path;
	void backtracking(vector<int> nums,vector<bool>& used)
	{
		if(path.size() == nums.size())
		{
			ans.push_back(path);
			return;
		}
		unordered_set<int> uset;
		for(int i = 0; i < nums.size(); i++)
		{
			if(used[i] == true) continue;
			if(uset.find(nums[i]) != uset.end()) continue;
			path.push_back(nums[i]);
			uset.insert(nums[i]);
			used[i] = true;
			backtracking(nums,used);
			path.pop_back();
			used[i] = false;
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<bool> used(nums.size(),false);
		backtracking(nums,used);
		return ans;
	}
};
